package com.squirrel.michale.node;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/1/19 8:49 PM
 * @company Michale Squirrel
 * @link
 * @description
 *
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 * 示例 2：
 *
 *
 * 输入：head = [1,2]
 * 输出：[2,1]
 * 示例 3：
 *
 * 输入：head = []
 * 输出：[]
 *
 *
 * 提示：
 *
 * 链表中节点的数目范围是 [0, 5000]
 * -5000 <= Node.val <= 5000
 *
 *
 * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
 */
public class Example001_LeetCode0206 {


    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }


    public ListNode reverseList2(ListNode head) {

        // 把head 和 result 交换 使用了tempNode这个中间变量

        ListNode result = null;
        ListNode tempNode = null;
        while (head != null) {
            // 为tempNode赋值  用tempNode把下一个节点保存起来
            tempNode = head.next;
            // 反转的核心代码 把下一个节点的值改成result
            head.next = result;
            // 为下一轮result赋值
            result = head;
            // 为下一轮head赋值 把header的值改为temp
            head = tempNode;
        }
        return result;

    }

    public ListNode reverseList3(ListNode head) {
        //递归终止条件是当前为空，或者下一个节点为空
        if(head==null || head.next==null) {
            return head;
        }
        //这里的cur就是最后一个节点
        ListNode cur = reverseList3(head.next);
        //这里请配合动画演示理解
        //如果链表是 1->2->3->4->5，那么此时的cur就是5
        //而head是4，head的下一个是5，下下一个是空
        //所以head.next.next 就是5->4
        head.next.next = head;
        //防止链表循环，需要将head.next设置为空
        head.next = null;
        //每层递归函数都返回cur，也就是最后一个节点
        return cur;
    }

//    作者：王尼玛
//    链接：https://leetcode.cn/problems/reverse-linked-list/solutions/36710/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


    /**
     * 妖魔化的双指针
     * 原链表的头结点就是反转之后链表的尾结点，使用 headheadhead 标记 .
     * 定义指针 curcurcur，初始化为 headheadhead .
     * 每次都让 headheadhead 下一个结点的 nextnextnext 指向 curcurcur ，实现一次局部反转
     * 局部反转完成之后，curcurcur 和 headheadhead 的 nextnextnext 指针同时 往前移动一个位置
     * 循环上述过程，直至 curcurcur 到达链表的最后一个结点 .
     *
     * 作者：路漫漫我不畏
     * 链接：https://leetcode.cn/problems/reverse-linked-list/solutions/99711/fan-zhuan-lian-biao-shuang-zhi-zhen-di-gui-yao-mo-/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param head
     * @return
     */
    public ListNode reverseList4(ListNode head) {
        //递归终止条件是当前为空，或者下一个节点为空
        if(head==null ) {
            return null;
        }
        ListNode result = head;
        ListNode tempNode = null;
        while (head.next != null) {

            tempNode = head.next.next;
            head.next.next = result;
            result = head.next;
            head.next = tempNode;

        }
        return result;

    }
    private static void swap(int[] arr, int i, int j) {
        // 把i的值先保存起来
        int temp = arr[i];
        // 把i的值改成j
        arr[i] = arr[j];
        // 把j的值改成temp
        arr[j] = temp;
    }


//    public static DoubleNode reverseDoubleList(DoubleNode head) {
//        DoubleNode pre = null;
//        DoubleNode next = null;
//        while (head != null) {
//            next = head.next;
//            head.next = pre;
//            head.last = next;
//            pre = head;
//            head = next;
//        }
//        return pre;
//    }


    public static void main(String[] args) {
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));

        Example001_LeetCode0206 no001LeetCode0206 = new Example001_LeetCode0206();
        System.out.println(listNode);
//        System.out.println(no001LeetCode0206.reverseList2(listNode).toString());
        System.out.println(no001LeetCode0206.reverseList4(listNode).toString());
    }




}
